# @algorithm @lc id=2104 lang=python3 weekname=biweekly-contest-60
# @title operations-on-tree
from typing import List
class Node:
    def __init__(self, i):
        self.locker = 0
        self.father = None
        self.children = []
        self.LockedParent = 0
        self.LockedChildren = 0
        self.loc = i
        
def addLockParent(tmp, value):
    tmp.LockedParent+=value
    for tmpChildren in tmp.children:
        addLockParent(tmpChildren)

class LockingTree:

    def __init__(self, parent: List[int]):
        
        
        self.n = len(parent)
        self.NodeList = [Node(i) for i in range(self.n)]
        for i, v in enumerate(parent):
            if not i:
                continue
            self.NodeList[i].father = self.NodeList[v]
            self.NodeList[v].children.append(self.NodeList[i])
        # for i in self.NodeList:
        #     if i.father:
        #         print(i.father.loc)
            
            


    def lock(self, num: int, user: int) -> bool:
        if self.NodeList[num].locker==0:
            self.NodeList[num].locker=user
            father = self.NodeList[num].father
            # print('haha')
            while father:
                father.LockedChildren += 1
                father = father.father
                # print(father)
            for child in self.NodeList[num].children:
                addLockParent(child, 1)
            return True
        return False


    def unlock(self, num: int, user: int) -> bool:
        if self.NodeList[num].locker==user:
            self.NodeList[num].locker = 0
            father = self.NodeList[num].father
            if father:
                father.LockedChildren -= 1
                father = father.father
            for child in self.NodeList[num].children:
                addLockParent(child, -1)
            return True
        return False
            


    def upgrade(self, num: int, user: int) -> bool:
        tmpNode = self.NodeList[num]
        if tmpNode.locker == 0 and tmpNode.LockedParent==0 and tmpNode.LockedChildren>0:
            tmpNode.locker = user
            father = self.NodeList[num].father
            # 所有父节点，增加一个锁上的子孙节点，减去要开锁的孩子节点
            if father:
                father.LockedChildren += 1-tmpNode.LockedChildren
                father = father.father
            # 解锁所有子孙节点
            def unlockchildren(tmp, lockedParent):
                tmp.locker = 0
                tmp.LockedParent = lockedParent
                for tmpChild in tmp.children:
                    unlockchildren(tmpChild, lockedParent)
            for tmp in tmpNode.children:
                unlockchildren(tmp, tmpNode.LockedParent+1)
                
            return True
        return False

if __name__=='__main__':
    parents = [-1, 0, 0, 1, 1, 2, 2]
    lockTree = LockingTree(parents)
    print(lockTree.lock(2, 2))
    print(lockTree.unlock(2, 2))
    print(lockTree.lock(2, 2))
    print(lockTree.upgrade(0, 1))
    print(lockTree.lock(0, 1))

